「NOIP 2024」编辑字符串

首先这是一道一眼就可以看出来的贪心题，毕竟你也想不到任何其他方法去解了对吧

我们可以注意到表示交换的字符串被1分成了几段，每一段的数字都可以任意交换位置

然后十分贪心的想，我们只要能把该段的一个数交换过来匹配一定不会变劣，因为与其等到后面再交换还不如现在就匹配，抑或是将不匹配点延后罢了

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair< int,int >
#define QWQ return 0;

const int N=1e5+10;

int tp1[N], tp2[N];
int vis1[N][2], vis2[N][2];
bool use1[N], use2[N];

void sovel()
{
	int n;
	string s1, t1;
	string s2, t2;
	cin>>n>>s1>>s2>>t1>>t2;
	s1=" "+s1, s2=" "+s2,
	t1=" "+t1, t2=" "+t2;
	int ans=0, cnt1=0, cnt2=0;
	bool flag1=0, flag2=0;
	for( int i=1;i<=n;i++ )
		tp1[i]=tp2[i]=
		vis1[i][0]=vis1[i][1]=
		vis2[i][0]=vis2[i][1]=
		use1[i]=use2[i]=0;
	for( int i=1;i<=n;i++ )
		if( t1[i] == '1' )
		{
			if( !flag1 )       ++cnt1, flag1=true;
			if( s1[i] == '0' ) ++vis1[cnt1][0];
			else               ++vis1[cnt1][1];
			tp1[i]=cnt1;
		}
		else flag1=false;
	for( int i=1;i<=n;i++ )
		if( t2[i] == '1' )
		{
			if( !flag2 )       ++cnt2, flag2=true;
			if( s2[i] == '0' ) ++vis2[cnt2][0];
			else               ++vis2[cnt2][1];
			tp2[i]=cnt2;
		}
		else flag2=false;
	for(int i=1;i<=n;i++)
	{
		if(  tp1[i] &&  tp2[i] )
		{
			if     ( vis1[tp1[i]][1] && vis2[tp2[i]][1] ) --vis1[tp1[i]][1], --vis2[tp2[i]][1], ++ans;
			else if( vis1[tp1[i]][0] && vis2[tp2[i]][0] ) --vis1[tp1[i]][0], --vis2[tp2[i]][0], ++ans;
		}	
		if(  tp1[i] && !tp2[i] )
		{
			if     ( s2[i] == '0' && vis1[tp1[i]][0] ) --vis1[tp1[i]][0], ++ans;
			if     ( s2[i] == '1' && vis1[tp1[i]][1] ) --vis1[tp1[i]][1], ++ans;	
		}
		if( !tp1[i] &&  tp2[i] )
		{
			if     ( s1[i] == '0' && vis2[tp2[i]][0] ) --vis2[tp2[i]][0], ++ans;
			if     ( s1[i] == '1' && vis2[tp2[i]][1] ) --vis2[tp2[i]][1], ++ans;	
		}
		if( !tp1[i] && !tp2[i] && s1[i] == s2[i] ) ++ans;
	}
	cout<<ans<<"\n";
}

int main()
{
	// freopen( "edit.in","r",stdin );
	// freopen( "edit.out","w",stdout );
	ios::sync_with_stdio( false );
	cin.tie( nullptr ), cout.tie( nullptr );
	int t;
	for( cin>>t;t;t-- ) sovel();
	QWQ
}